#pragma once

#include <iostream>
#include <string>
#include <vector>

namespace MyHash {
template <class T>
struct HashNode {
  T _data;
  HashNode<T>* _next;

  HashNode(const T& data) : _data(data), _next(nullptr) {}
};

template <class K>
struct HashFunc { /*仿函数 用于将数据进行size_t化*/
  size_t operator()(const K& key) { return key; }
};

template <>
struct HashFunc<std::string> { /*仿函数 用于将数据进行size_t化*/
  // 该处的仿函数需要使用字符串哈希的方式来确认整个string字符串的ASCII大小
  size_t operator()(const std::string& str) {
    size_t hash = 0;
    for (auto ch : str) {
      hash += ch;
      hash *= 31;
    }
    return hash;
  }
};

template <class K, class T, class KeyOfT, class Hash>
class HashTable;  // 前置声明

// 1.先实现迭代器(各个函数基本上都与迭代器有关
// 不想修改的话那就先对迭代器进行封装)
template <
    class K /*键值*/, class T /*数据*/, class Ref /*引用 用于 opoerator* */,
    class Ptr /*指针 用于operator->*/, class KeyOfT,
    class
    Hash /*仿函数 该模板参数以及前一个模板参数KeyOfT都是用于实例化哈希表*/>

struct __Hash_Iterator {
  friend class HashTable<K,T,KeyOfT,Hash>;

  // 单向迭代器 只需要实现++
  typedef HashTable<K, T, KeyOfT, Hash> HsTable;
  typedef __Hash_Iterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
  typedef __Hash_Iterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
  typedef HashNode<T> Node;



  // 两个构造函数
  __Hash_Iterator(Node* node, HsTable* ht) : _Ht(ht), _node(node){}
  __Hash_Iterator(const Iterator& it) : _Ht(it._Ht), _node(it._node) {}

  // operator++();
  Self& operator++() {
    if (_node->_next != nullptr) {
      _node = _node->_next;
    } else {
      // 找下一个不为空的桶
      KeyOfT kot;
      Hash hash;
      // 算出我当前的桶位置
      size_t hashi = hash(kot(_node->_data)) % _Ht->_hashTable.size();
      ++hashi;
      while (hashi < _Ht->_hashTable.size()) {
        if (_Ht->_hashTable[hashi]) {
          _node = _Ht->_hashTable[hashi];
          break;
        } else {
          ++hashi;
        }
      }

      // 没有找到不为空的桶
      if (hashi == _Ht->_hashTable.size()) {
        _node = nullptr;
      }
    }

    return *this;
  }

  // operator*();
  Ref operator*() { return _node->_data; }

  // operator->();
  Ptr operator->() { return &_node->_data; }

  // operator==();
  bool operator==(const Iterator& it) { return it._node == _node; }

  // operator!=();
  bool operator!=(const Iterator& it) { return it._node != _node; }

  // 需要哈希表本体
  HsTable* _Ht;
  Node* _node;  // 节点指针
};

template <class K /*键值*/, class T /*数据类型(pair或者K)*/,
          class KeyOfT /*仿函数 用于取出data中的Key*/,
          class Hash = HashFunc<K> /*仿函数 用于将数据进行size_t化*/>
class HashTable {
  friend struct __Hash_Iterator<
      K, T, T&, T*, KeyOfT, Hash>;  // 避免友元声明时出现的"模板参数阴影"问题

 public:
  typedef __Hash_Iterator<K, T, T&, T*, KeyOfT, Hash> iterator;
  typedef __Hash_Iterator<K, T, const T&, const T*, KeyOfT, Hash>
      const_iterator;

  typedef HashNode<T> Node;
  iterator begin() {  // 普通版本迭代器
    Node* cur = nullptr;
    size_t i = 0;
    for (; i < _hashTable.size(); ++i) {
      if (_hashTable[i]) {
        cur = _hashTable[i];
        break;
      }
    }
    if (cur) {
      return iterator(cur, this);
    }
    return iterator(nullptr, this);
  }

  ~HashTable() {
    Node* cur = nullptr;
    for (size_t i = 0; i < _hashTable.size(); ++i) {
      if (_hashTable[i]) {
        cur = _hashTable[i];
        Node* next = cur->_next;
        while (cur) {
          delete cur;
          cur = next;
        }
      }
    }
  }

  iterator end() { return iterator(nullptr, this); }  // 普通版本迭代器

  const_iterator begin() const {  // const版本迭代器
    size_t i = 0;
    Node* cur = nullptr;
    for (; i < _hashTable.size(); ++i) {
      if (_hashTable[i]) {
        cur = _hashTable[i];
        break;
      }
    }
    if (cur) {
      return iterator(cur, this);
    }
    return iterator(nullptr, this);
  }

  const_iterator end() const {
    return iterator(nullptr, this);
  }  // const版本迭代器

  std::pair<iterator, bool> Insert(const T& data) {

    KeyOfT kot;
    Hash hash;


    iterator isIn = Find(kot(data));//判断该数据是否存在 若是存在则不进行插入
    if (isIn != end()){
      return  std ::make_pair(iterator(nullptr, this), false);
    }

      if (_hashTable.size() == _n) {  // 负载因子 == 1 需要进行扩容
        size_t newSize = GetNextPrime(_hashTable.size());  // 获取新的节点大小
        std::vector<Node*> newTable(newSize,nullptr);

        for (size_t i = 0; i < _hashTable.size(); ++i) {
          Node* cur = _hashTable[i];
          while (cur) {
            Node* next = cur->_next;

            size_t hashi = hash(kot(cur->_data)) % newTable.size();
            cur->_next = newTable[hashi];
            newTable[hashi] = cur;
            cur = next;
          }
          _hashTable[i] = nullptr;
        }
        _hashTable.swap(newTable);
      }

    size_t hashi = hash(kot(data)) % _hashTable.size();
    Node* newnode = new Node(data);
    newnode->_next = _hashTable[hashi];
    _hashTable[hashi] = newnode;
    _n++;
    return std ::make_pair(iterator(newnode, this), true);
  }

  iterator Find(const K& key) {
    Hash hash;
    KeyOfT kot;

    if (_hashTable.size() == 0) return end();
    size_t hashi = hash(key) % _hashTable.size();
    Node* cur = _hashTable[hashi];
    while (cur) {
      if (kot(cur->_data) == key) {
        return iterator(cur, this);
      }
      cur = cur->_next;
    }
    return end();
  }

  bool Erase(const K& key) {
    Hash hash;
    KeyOfT kot;

    size_t hashi = hash(key) % _hashTable.size();

    Node* prev = nullptr;
    Node* cur = _hashTable[hashi];

    while(cur){
        if(kot(cur->_data) == key){
            if(prev == nullptr){
              _hashTable[hashi] = cur->_next;
            }
            else{
              prev->_next = cur->_next;
            }
            --_n;
            delete cur;
            return true;
        }
        else{
          prev = cur;
          cur = cur->_next;
        }
    }
    return false;
  }

  size_t GetNextPrime(size_t prime) {
    static const int __stl_num_primes = 28;
    static const unsigned long __stl_prime_list[__stl_num_primes] = {
        53,        97,         193,        389,       769,       1543,
        3079,      6151,       12289,      24593,     49157,     98317,
        196613,    393241,     786433,     1572869,   3145739,   6291469,
        12582917,  25165843,   50331653,   100663319, 201326611, 402653189,
        805306457, 1610612741, 3221225473, 4294967291};

    size_t i = 0;
    for (; i < __stl_num_primes; ++i) {
      if (__stl_prime_list[i] > prime) {
        return __stl_prime_list[i];
      }
    }
    return __stl_prime_list[i];
  }

 protected:
 private:
  size_t _n = 0;  // 负载因子
  std::vector<Node*> _hashTable;
};
}  // namespace MyHash